package 力扣._6940_链表中插入最大公约数;

import 力扣.公用数据结构.ListNode;

public class Solution {

    //辗转相除法
    int maxyue(int a, int b) {
        if (a < b) {
            int t = a;
            a = b;
            b = t;
        }
        int k = 0;
        do {
            k = a % b;
            a = b;
            b = k;
        } while (k != 0);
        return a;
    }

    public ListNode insertGreatestCommonDivisors(ListNode head) {
        ListNode pre = head, p;
        if (pre != null)
            p = pre.next;
        else
            return head;
        while (p != null) {
            //在pre p之间插入
            int k = maxyue(p.val, pre.val);
            ListNode t =new ListNode(k,p);
            pre.next = t;
            pre = p;
            p = p.next;
        }
        return head;
    }
}
